﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0047_MaxSubArray : IAlgorithm
    {
        // 最大子序和

        // 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

        // 子数组 是数组中的一个连续部分。

        //提示：
        //1 <= nums.length <= 10^5
        //-10^4 <= nums[i] <= 10^4

        //进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 5, 4, -1, 7, 8 };
            // 算法执行与打印
            Console.WriteLine(MaxSubArray(nums));
        }

        // 算法
        public int MaxSubArray(int[] nums)
        {
            var last = nums[0];
            int sum = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                sum = Math.Max(sum, nums[i] + Math.Max(last, 0));
                last = nums[i] + Math.Max(last, 0);
            }
            return sum;
        }
    }
}
